/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-03-29
 * Time: 10:42
 */
//举例： arr = {3,2,5} arr的min为2，max为10，
 //      在区间[2,10]上，4是不能被任何一个子集相加得到的值中最小的，所以4是arr的最小不可组成和；
public class Solution2 {
  /*  先找到数组中的最小值min，以及元素最大和add；
    按照0/1背包问题，我们可以列出如下表格：
    j表示组成和也就是背包的容量的组成情况，a[i]表示前i个物品任意选放的最大价值，i表示物品下标，dp[j]表示背包容量为j时，
    背包的最大价值（01背包问题可以选择放入物品和不放，只需选择最大价值的那个）
    遍历背包数组，直到最后如果可以组成相应背包，那么dp[j]值也就是背包的价值应该和背包此时的容量是一样的，如果有不一样的，
    那么第一个出现的就是最小不可组成和
    例如：3  2  5
    定义一个价值容器：
                 j   0  1  2  3  4  5  6  7  8  9  10
            i  a[i]
            0   3    0  0  0  3  3  3  3  3  3  3   3
            1   2    0  0  2  3  3  5  5  5  5  5   5
            2   5    0  0  2  3  3  5  5  7  8  8   10

    上面表格中，每一行都是对上一行元素的覆盖更新，从后往前放，用低价值更新高价值*/
    public static  int getFirstUnFormedNum(int[] arr) {
        int minSum=Integer.MAX_VALUE;
        int maxSum=0;
        for(int i = 0; i < arr.length; i++){
            if(minSum>arr[i]){
                minSum = arr[i];
            }
            maxSum+=arr[i];
        }
        int[]dp=new int[maxSum+1];
        dp[0]=0;
        for(int i = 0;i<arr.length; i++){
            for(int j=maxSum;j >=arr[i];--j) {  //对于背包容量小于物品重量的直接跳过，肯定是装不下的
                dp[j]=Math.max(dp[j-arr[i]]+arr[i],dp[j]); //对于01背包问题，存在取和不取的情况，取一个最大值即可
            }
        }
        for(int j=minSum;j<=maxSum;j++){
            if(dp[j]!=j){
                return j;
            }
        }
        return maxSum+1;

    }
    public static void main(String[] args) {
        int[] arr={2,3,5};
        System.out.println(getFirstUnFormedNum(arr));

    }
}
